package leetcode_jz_offer;

/**
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 * 返回 你可以获得的最大乘积 。
 **/

/**
 * dp[i] 表示将正整数i拆分成至少两个正整数的和之后，这些正整数的最大乘积
 * 特别地,0不是正整数,1是最小的正整数,0和1都不能拆分，因此dp[0]=dp[1]=0
 * 当i≥2时，假设对正整数i拆分出的第一个正整数是j（1≤j<i），则有以下两种方案：
 * 将i拆分成j和i−j的和，且i−j不再拆分成多个正整数，此时的乘积是j×(i−j)；
 * 将i拆分成j和i−j的和，且i−j继续拆分成多个正整数，此时的乘积是j×dp[i−j]
 */
public class Num343_整数拆分 {
    public int integerBreak(int n) {
        final int M=1000000007;
        int[] dp=new int[n+1];
        for (int i = 2; i <= n; i++) {
            int resMax=0;
            for (int j = 0; j < i; j++) {
                resMax=Math.max(resMax,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=resMax;
        }
        return dp[n];
    }
}
